Pépin's test

In mathematics, Pépin's test is a primality test, which can be used to determine whether a Fermat number is prime. It is a variant of Proth's test. The test is named for a French mathematician, Théophile Pépin.

Contents

Description of the test

Let F_n=2^{2^n}%2B1 be the nth Fermat number. Pépin's test states that for n > 0,

F_n is prime if and only if 3^{(F_n-1)/2}\equiv-1\pmod{F_n}.

The expression 3^{(F_n-1)/2} can be evaluated modulo F_n by repeated squaring. This makes the test a fast polynomial-time algorithm. However, Fermat numbers grow so rapidly that only a handful of Fermat numbers can be tested in a reasonable amount of time and space.

Other bases may be used in place of 3, for example 5, 6, 7, or 10 (sequence A129802 in OEIS).

Proof of correctness

For one direction, assume that the congruence

3^{(F_n-1)/2}\equiv-1\pmod{F_n}

holds. Then 3^{F_n-1}\equiv1\pmod{F_n}, thus the multiplicative order of 3 modulo F_n divides F_n-1=2^{2^n}, which is a power of two. On the other hand, the order does not divide (F_n-1)/2, and therefore it must be equal to F_n-1. In particular, there are at least F_n-1 numbers below F_n coprime to F_n, and this can happen only if F_n is prime.

For the other direction, assume that F_n is prime. By Euler's criterion,

3^{(F_n-1)/2}\equiv\left(\frac3{F_n}\right)\pmod{F_n},

where \left(\frac3{F_n}\right) is the Legendre symbol. By repeated squaring, we find that 2^{2^n}\equiv1\pmod3, thus F_n\equiv2\pmod3, and \left(\frac{F_n}3\right)=-1. As F_n\equiv1\pmod4, we conclude \left(\frac3{F_n}\right)=-1 from the law of quadratic reciprocity.

References

External links